


/**
* PriorityQueue interface.
* Some priority queues may support a decreaseKey operation,
* but this is considered an advanced operation. If so,
* a Position is returned by insert.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public interface PriorityQueue {
	 /**
	  * The Position interface represents a type that can
	  * be used for the decreaseKey operation.
	  */
	 public interface Position {
	     /**
	      * Returns the value stored at this position.
	      * @return the value stored at this position.
	      */
	     Comparable getValue( );
	 }
	 
	 /**
	  * Insert into the priority queue, maintaining heap order.
	  * Duplicates are allowed.
	  * @param x the item to insert.
	  * @return may return a Position useful for decreaseKey.
	  */
	 Position insert( Comparable x );
	 
	 /**
	  * Find the smallest item in the priority queue.
	  * @return the smallest item.
	  * @throws UnderflowException if empty.
	  */
	 Comparable findMin( );
	 
	 /**
	  * Remove the smallest item from the priority queue.
	  * @return the smallest item.
	  * @throws UnderflowException if empty.
	  */
	 Comparable deleteMin( );
	 
	 /**
	  * Test if the priority queue is logically empty.
	  * @return true if empty, false otherwise.
	  */
	 boolean isEmpty( );
	 
	 /**
	  * Make the priority queue logically empty.
	  */
	 void makeEmpty( );
	 
	 /**
	  * Returns the size.
	  * @return current size.
	  */
	 int size( );
	 
	 /**
	  * Change the value of the item stored in the pairing heap.
	  * This is considered an advanced operation and might not
	  * be supported by all priority queues. A priority queue
	  * will signal its intention to not support decreaseKey by
	  * having insert return null consistently.
	  * @param p any non-null Position returned by insert.
	  * @param newVal the new value, which must be smaller
	  *    than the currently stored value.
	  * @throws IllegalArgumentException if p invalid.
	  * @throws UnsupportedOperationException if appropriate.
	  */
	 void decreaseKey( Position p, Comparable newVal );
	}